# -*- coding: utf-8 -*-
# Created on Sun May 05 17:06:01 2013
# MergeSort, page 29,32


# A is a array, Merge A[p, q] and A[q+1, r]; p < q < r
def Merge(A, p, q, r):
    n1 = q-p+1
    n2 = r-q
    L = []
    R = []
    for i in range(0, n1):
        L.append(A[p+i])
    for j in range(0, n2):
        R.append(A[q+j+1])
    
    i=0
    j=0
    for k in range(p, r+1):            
        if (j >= n2) or ((i < n1) and (L[i] < R[j])):
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def MergeSort(A, p, r):
    if p < r:
        q = (p+r)/2
        MergeSort(A, p, q)
        MergeSort(A, q+1, r)
        Merge(A, p, q, r)
        
if __name__ == '__main__':
    A = [ 2, 4, 5, 7, 1, 2, 3, 6]
    MergeSort(A, 0, len(A)-1)
    output = '['
    for a in A:
        output += str(a)+','
    print output+']'
